CMSC 198I: The Science behind Computing: What makes Web Search, Navigation Systems and Social Media work?

Spring 2011

Section 0101 and 0102

Home | Syllabus/Homeworks | Lecture Notes | Resources | Group Presentations

Notes These are the current set of notes (about 50 pages!). I would suggest that you start reading these. The order of coverage may vary, but I do exepct everyone to read the Introduction and also the sections on computing square-roots as well as the stable marriage problem.

The notes given here are not a substitute for attending class. They are meant to supplement the lectures. Please keep this in mind.

Lecture Notes (Click Notes above to get notes)

Week 1Introduction to Computer Science, Stable Marriage, and Bipartite Matching slides Ruby codes Product of numbers, Sum of numbers
Week 2Introduction to Euclid's GCD and proofs No slides Ruby codes GCD, Print N integers, Print sum of N integers
Week 3 Introduction to Graphs and Web Search Read first 10 pages Slides, Ruby codes Power of 2, Fibonacci numbers
Week 4 Arrays and Graphs Pos/Neg Count FindingMax Create a Graph (can you guess what the loop does?) Read Piazzza! Ruby codeDeg > 2
Week 5Sorting and Searching
Arrays and Binary Search
Binary Search Animation
Sorting Animation
Binary Search in Ruby
Week 6 Exam 1 (Feb 28th, 2011) ( Avg 36.625) Sample Exam
Guest Lecture
Increasing order
Week 7 Mathematical Induction and Sorting Induction Notes Insertion Sort code,
Insertion Sort detailed code
Week 8 Sorting and Guest Lecture Sorting
P2P Overview Guest Lecture
HW 5 project assignments
Week 9 Induction and Guest lecture on P2P (Keleher) Induction Notes
P2P Guest lecture
Video on Search
Recursive factorial
Merge sort
Merge sort detailed
Week 10 Writing Recursive Programs and Hashing Recursive Square root
Recursive Fibonacci
Ascii codes
Hash function
Recursive Array sum
Week 11 Exam 2 (Apr 11) DFS/Group Presentations
Week 12 DFS + Shortest Paths DFS (code) Cycle Detection
Week 13 Shortest Paths + Cryptography Crypto Notes Cipher code
Decryption code
Recursive Array element print
Recursive Binary Search
Square root count
Sign up sheet
Week 14 AI lecture + Internet Lecture
Week 15 Crytography and Complexity No Notes Bubble Sort Quick Sort