LECT: topics: A L G O R I T H M S 1 introduction what is computer science 1000-level courses 2 more formal definition of algorithm example algorithms 3 more example algorithm stable marriage algorithm proof that stable marriage algorithm works HW 0 DUE 4 spreadsheets more algorithms linear search algorithm find largest algorithm primitive operations 5 another example algorithm personal reasons to take the course binary numbers lightbulb puzzle HW 1 (Spreadsheet) DUE H A R D W A R E 6 converting from base 2 to base 10 bytes bits as voltage discrete vs continuous 7 boolean logic "This statement is a lie." truth tables logic gates - how build with transistors abstracting from design details compare-for-equality circuit, abstraction thereof 8 digital circuits decoder and multiplexor circuits HTML 9 Stinky full adder circuit! 10 intial intro to computer organization 11 computer hardware song: "Digital Love" intro to computer organization HW 2 (html and Stinky) DUE 12 more computer organization 13 operating systems 14 machine language database queries with Unix shell pipelines P R O G R A M M I N G 15 finish database queries Java intro: compiler, source code syntax versus semantics midterm review MIDTERM EXAM March 9 16 midterm solutions more Java examples: loops HW 3 (databases) DUE 17 more loops nested conditionals 18 guess the number -- binary search guess the animal (20 questions) prime numbers complexity intro 19 bubble sort debugging rules of thumb debugging song 20 nested loops 21 more nested loops complexity/efficiency of algorithms HW 4 (Java) DUE Info about HW5: Othello -- requires nested loops T H E O R Y A N D A R T I F I C I A L I N T E L L I G E N C E 22 Guest lecture on anomoly detection by Eleazar Eskin 23 review technical info about HW5's Othello How to access the board.board array nested loops 24 more nested loops intro to computational models Computability: Turing Machines and The Halting Problem 25 Recursion Mergesort -- faster than Bubble sort "Little Harmonic Labyrinth" story Stinky fractals -- Sierpinsky's triangle 26 Life (cellular automata) online demo Special bonus: it is Turing-complete! meta pi 27 Leftover recursion: online demos of sorting algorithms summary of topics and themes of the course final exam review HW 5 (Java) DUE FINAL: COMS W1001 001 INTRODUCTION TO COMPUTERS Siegel May 9 TUES HAV 209 900 AM 1200 PM

**email:** *evs at cs dot columbia dot edu*