Algorithm Design and Analysis

Lectures: Conf.dr.ing Ioana Sora

Content of Lectures and Labs

Curent lecture schedule and current lab assignments on Campus Virtual

These are the topics to be discussed, with bibliographic pointers, lecture slides and lab exercises.

Week	Topics	Bibliography	Lecture Notes	Lab exercises
Week 1	Intro to Design and Analysis of Algorithms: (Course Goals, Course Administration) Complexity Analysis: short review Data structures: short review	[CLRS]-chap 3, chap 4.3, 4.4,4.5	slides (Intro) slides(Review Complexity Analysis) slides(Review DataStructures)	Programming review and Complexity analysis exercises
Week 2	Data structures: Binary Search Trees	[CLRS]-chap 12	slides (Binary Search Trees)	BST exercises
Week 3	Data structures: Balancing Binary Search Trees (AVL trees)		slides	Balanced binary trees exercises
Week 4	Data structures: Different Tree Based Data Structures		slides	Various tree based data structures exercises Optional tool project 1 Optional tool project 2
Week 5	Great algorithms solving real life problems: Data Compression (Huffman, Adaptive Huffmann, LZV)	[Unlocked]-Chap 9, [CLRS]-Chap 16.3	slides	Compression algorithms exercises Optional tool project 3
Week 6	Correctness of Algorithms. Induction.	[Manber]-Chap 2, [CLRS]-Chap 2.1	Lecture Slides Example - Proof Huffman
Week 7	Design strategies: Design of Algorithm by Induction - part 1	[Manber]-Chap 5)	slides	Design by induction exercises
Week 8	Design strategies illustrated: Growing Minimum Spanning Trees Fundamental data structures: Graphs Algorithms: Prim's algorithm for MST	[CLRS]- Subchap 22.1 Representation of Graphs. [CLRS] - Chap 23	slides (Graphs) slides (MST)	Minimum spanning trees exercises
Week 9	Data structures: Disjoint-sets ([CLRS] - chap 21) Algorithms: MST revisited - Kruskal's algorithm	[CLRS] - chap 21	slides	Minimumspanning trees exercises
Week 10	Design strategies: Design of Algorithm by Induction - part 2. Dynamic Programming	[Manber]-Chap 5, [CLRS] - Chap 15	slides	Dynamic programming exercises
Week 11	A dynamic programming problem: Shortest paths in graphs Algorithms: Bellman-Ford, Dijkstra, Floyd-Warshall	[CLRS]-chap 24, [CLRS]-chap 25	slides	Shortest paths exercises
Week 12	Graph algorithms: Graph Traversals (DFS, BFS)	[CLRS]-Chap 22	slides	Graph traversals exercises
Week 13	Graphs: Applications of DFS (Articulation Points, Bridges, Biconnected Components, Strongly Connected Components, Topological Sorting)		slides	DFS applications exercises
Week 14

Textbooks

	[CLRS]	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd Ed, MIT Press, 2009.
	[Unlocked]	Thomas Cormen, Algorithms Unlocked, MIT Press, 2013.
	[Manber]	Udi Manber, Introduction to Algorithms - A Creative Approach , Addison Wesley 1989
	[McCormick]	John McCormick, Nine Algorithms that Changed The Future , Princeton University Press, 2012.

Lab

• Questions - to be solved with pen on paper
  Examples:
  • The sequence of numbers 5 9 26 3 1 2 is inserted into an initially empty AVL tree. Draw the tree after each insertion.
  • The following sequence of code is said to do ...whatever... Show that the algorithm is correct or show that the algorithm is incorrect.
  • A sequence of code/algorithm is given. Analyse its time complexity.
• Simple implementations - implement something that is described in the course (BST, shortest path, etc)
• Algorithm design problems
  Examples:
  • A problem with a simple brute-force solution is given. Find a better solution. (Example: something like the Celebrity problem - [Manber]-Chap 5.5).
  • An extension/change in one of the algorithms discussed in the lectures
  • This kind of assignments require to:
    1. Describe the proposed algorithm (free text, explanations, examples, pseudocode)
    2. Demonstrate and analyze your algorithm
    3. Implement the algorithm

Optional projects

Examination policy

Final grade = 2/3 (final exam + bonus points) + 1/3 lab grade