# Better Informatics

### ADS - Algorithms and Data Structures | drps, info, papers December exam Edit on GitHub

• See shared drive for some unofficial solutions.
• An unofficial set of programming assignments based on the ADS material - website
• Sorting algorithms 1 - interactive
• Sorting algorithms 2 - website
• Counting sort - interactive
• A video clearly demonstrating the Counting Sort (as it’s not in the above link, and Mary’s notes don’t make it easy) - video
• Prim’s Algorithm - interactive
• Kruskal’s Algorithm - interactive
• Longest Common Subsequence - animation
• Network Flow - interactive
• Graham’s Scan - interactive

### FNLP - Foundations of Natural Language Processing Edit on GitHub

• (2019-20) Bora’s Notes
• See shared drive for past papers and solutions. Addtional resources on discourse coherence:
• http://homepages.inf.ed.ac.uk/alex/papers/iwcs4.pdf
• https://www3.cs.stonybrook.edu/~ychoi/cse507/slides/06-discourse.pdf
• All slides (2014) in one pdf
• 14/15 slides rough summary: here (Directly exported from org-mode, so algorithms and formulas are largely missing)

### IDB - Introduction to Databases | drps, info, papers December exam Edit on GitHub

Previously named Database Systems (DBS)

• Normal Form checker (both BCNF and 3NF)
• Revision notes by Ben Shaw
• Relational algebra calculator / engine, example schema definition for tutorial 1
• Exam tips:
• Don’t forget semicolons, they will knock marks off for this!
• They want to see efficient solutions!
• Derivation using the Armstrong’s axioms: all steps and axioms in your derivation should be clearly mentioned
• It’s also worth understanding that there could be multiple correct proofs for a given implication so detailed explanations would make it easier for marker
• Relational algebra questions: consider how your answer behaves when certain relations are empty (tutorial 1, question 3)
• Relational algebra FAQ:
• Operations only return unique tuples. That means if you project on a single column, each row will be unique. This is because (definition) “Relations (tables) are sets of records of the same length”
• easily consumable stuff by b0rk:
• SQL to XXX FAQ (for those with experience in SQL/NoSQL)
• Relational algebra:
• project (pi)
• select id, name, city from customers;
• RethinkDB (NoSQL) people will know this as .pluck
• select (sigma)
• select * from customers where name = 'Alice' or name = city
• RethinkDB (NoSQL) people will know this as .filter
• Unknowns / NULL
• Unknown is represented as NULL in SQL,
• unknown = unknown is really NULL = NULL,
• all comparisons where at least one of the arguments is NULL, evaluates to unknown (which, again, is NULL).

### SP - Speech Processing Edit on GitHub

Answers to multiple choice for past papers here.