Introduction to Computers

Syllabus

Subject to change (periodically modified)

Note: lectures and homeworks for this course runs two threads in parallel: (1) computer science topics in the order of the text book and (2) background knowledge for the homework projects (listed on the main web page).

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