CS242. Algorithms and Data Structures

Topic outline

• General
  

  General

  • Organization matters File
  • Examination questions File
• Module 1. Introduction to algorithms and data structures
  

  Module 1. Introduction to algorithms and data structures

  • Lecture 01. Introduction to the course File
  • Lecture 02. Sorting algorithms. File
  • Assignment 1
  • Sample source file for assignment 1
  • A series of short lectures about implementing dynamic linked lists in C++ (and C). URL
  • Lecture 03. Graphs: definifions, representations, basic operations on graphs. File
  • Lecture 04. Graph traversals, part 1 File
  • Lecture 05. Graph traversals, part 2 File
  • Assignment 2. Graph traversals
  • Test data for assignment 2 File
  • Text file input/output sample
  • Sample code/project for parsing string lines and implementing DFS/BFS File
  • Lecture 06. Graph traversals, part 3 File
  • Test 1 Quiz
• Module 2.Greedy algorithms. Divide-and-Conquer strategy.
  

  Module 2.Greedy algorithms. Divide-and-Conquer strategy.

  • Lecture 07. Greedy algorithms, part 1: concepts, MST, Kruskal File
  • Lecture 08. Greedy algorithms, part 2: MST, Prim's algorithm File
  • Lecture 09. Divide-and-Conquer strategy. MergeSort File
  • Assignment 3. Merge sort.
  • Lecture 10. Divide-and-Conquer. Multiplication File
  • Assignment 4. Fast exponentiation
  • Test 2 Quiz
• Module 3. Dynamic progamming
  

  Module 3. Dynamic progamming

  • Lecture 11. Dynamic programming: general concepts and scheme File
  • Lecture 12. Edit Distance, the Longest Common Subsequence File
  • Assignment 5. Edit distance
  • Test 3 Quiz
• Module 4. NP-hard problems
  

  Module 4. NP-hard problems

  • Lecture 13. NP-hard problems (concept). Travelling Salesman Problem File
  • Assignment 6. Brute-force algorithm for TSP
  • Test data for assignment 6 File
  • Lecture 14. Inexact algorithms, part 1 File
  • Lecture 15. Inexact algorithms, part 2 File
  • Test 4 Quiz