|
|
Advanced Programming and Algorithms
Yu's Elite Education
Chris Baldassano chrisb@princeton.edu |
Fall
2015
|
Class Summary
This class will explore advanced algorithms and data structures in computer science. Students should have previous experience with programming (in any language).
The tentative course schedule is:
- Sept 10: Introduction [slides]
- Sept 17: Sorting [slides]
- Sept 24: Dynamic programming
- Oct 1: Heaps [slides]
- Oct 8: Linked lists [slides]
- Oct 15: Hashing [slides]
- Oct 22: BST [slides]
- Oct 29: Machine Learning [slides]
- Nov 5: Graph algorithms 1 [slides]
- Nov 12: Graph algorithms 2 [slides]
- Nov 19: Game playing [slides]
- Dec 3: Procedural generation [slides]
- Dec 10: ACSL contest topics and review [slides]
- Dec 17: Final quizzes and wrapup
Assignments
- Due before class on Sept 17: Implement bubble sort (in any programming language). How long does it take to sort 1,000 numbers? What about 10,000 numbers? Email your code and the answers to these two questions to chrisb@princeton.edu. Also email me to let me know which day you would be able to attend a rescheduled December 10th class: December 7th (Mon) or 11th (Fri).
- Due before class on Sept 24: Generate a random list 10,000 integers between 1-100. Write a program that finds the mode (the most common number) of the list. What is the time complexity of your algorithm? Note: you can use an existing implementation of a sorting algorithm. Also: vote for rescheduling December 10th class: December 7th (Mon) or 11th (Fri).
- Due before class on October 1: Solve the Moovie Mooving dynamic programming problem in pseudocode. What is the time complexity of your algorithm?
- Due before class on October 15: Given a reference to some node in a sorted singly-linked circular list, find the median of the list.
- Due before class on October 22: Given a dictionary of all English words, output all groups of anagrams.
- Due before class on October 29: Given the root node of a BST, calculate the depth (longest path to a leaf node).
- Due before class on November 5: Download this file from the Titanic dataset, which gives age of each passenger and whether they survived (1) or died(0). Generate the best (one-layer) decision tree on this data that gives the highest accuracy.
- Due before class on November 12: Download the flight times table, which gives departing city/time and arriving city/time for each flight. Write a program to find the fastest way to get from one city to another, assuming we need 60 minutes between flights.
- Due before class on November 19: Solve the Superbull problem in pseudocode. Hint: if teams are nodes, tournament can be described by a spanning tree.
- Due before class on December 3rd: Modify the Tic-Tac-Toe minimax code to perform two turns per player.
- Due before class on December 10th: Try different order Markov chains at this website - what happens if the order is too small or too large?