Introduction to Computer Science

CSCI 170-01

Spring 2012 Semester

The course syllabus.

Instructor's Home Page and current schedule.

The reading assignments.

Definitions etc.

Two of the key ideas in this course is the notion of abstraction and the concept of an algorithm.

Other important definitions.

Here is a list of the algorithmic patterns and specific algorithms carefully studied during the semester.

A suggested guide to expressing one's algorithms in Python.

In addition to studying algorithms, we have also focused on computational complexity. Here are some links that help one understand this important concept

Webopedia - An useful encyclopedia of computer (science) terminology.

The Spring 2012 XU Karel/Scratch/Kodu Contest:

As an extra credit opportunity consider participating in the Spring 2011 XU Monty-Karel/Scratch/Kodu Programming Contest. The contest deadline is Tuesday, April 24, 2012.

Homework Assignments:

• Reflection Paper on "Hitchhiker's Guide to the Galaxy." (Due Thursday 4/26/12)
  
  
• Homework 12: Introduction to Computational Complexity. (Due Thursday 4/26/12)
  
  
• Homework 11: Playing with Pictures - II (Due 4/19/12)
  
  • Some jpeg's that might be useful: A green photo, a photo of a blank wall, a really bad red eye shot, a CTE mug (kind of a "brown photo"), and a moon scene.
  
  
• Homework 10: Playing with Pictures - I (4/10/12)
  
  
• Homework 9: List Algorithms in Python (Due 4/3/12)
  
  
• Homework 8: The Simple Computer (Due 3/22/12)
  The Examples from class.
  See below for other Simple Computer-based extra credit opportunities.
  
  
• Homework 7: Computer Pieces-Parts (Due 2/28/12)
  
  
• Homework 6: Representations (Due 2/21/12)
  
  
• Homework 5: Explore Scratch and construct your own version of a "Catch Me If You Can" game. (Due 2/16/12)
  To prepare for this assignment, download Scratch, install the program, work through the on-line tutorial (found under Support tab on the Scratch site), work through the MazeWalk2.sb program (right-click to download this Scratch pgm.) demonstrated in class, and try to create your own game. This is a self-directed learning activity and will not be covered in any serious depth via lecture/class.
  
  
• Homework 4: Karel Does Algorithms (Due 2/9/12)
  The babySaver.py, babySaver2.py and windowCloser.py programs developed in class.
  
  
• Homework 3: Karel Gets Class-y. (Due 2/2/12)
  Here is the Figure Eight Runner problem from class - a good example of Top-Down design
  
  
• Homework 2: Go Karel Go. (Due 1/26/12)
  For those having trouble running the world builder (Windows Vista/7 users), here are some prebuilt worlds to use: walkAroundBlock(Fig2-7).kwld, fetchNewspaper(Fig2-8).kwld, groceryPickUp(Fig2-10).kwld, and olympicTraining(Fig2-12).kwld
  Right-click-ing each file affords you the option to download and save the file.
  
  
• Homework 1: Boxing Priorities. (Due 1/19/12)
  

Extra Credit Opportunities:

• Provide a Big-Oh analysis of the amicable pairs algorithm. You may assume that the list contains n values, and that each value is between 2..m - due Tuesday 4/24/12
  
• Write a Simple Computer implementation of selection sort, and/or insertion sort and/or binary search - due Tuesday 4/24/12
  
• Write a Python function to "flip" a picture. Flipping a picture is to rotate it 180 degrees around to the left (or right) - due Tuesday 4/17/12
• Write a Python function to count the number of "amicable pairs" of numbers present in a list of integers. Two numbers, x and y are "amicable" if the proper divisors of x add up to y and the proper divisors of y add up to x. The proper divisors of a value z are all the integers between 1 and z-1 that evenly divide z. - due Tuesday 4/17/12
• Write a Python function that takes a list as input and returns the number of distinct pairs of identical values - due Thursday 4/12/12
• Write a Simple Computer implementation of "Find Largest." Your program should output the value of the largest of the 10 data cards. An even harder version of the problem would be to output both the value AND its index in the input list. - due Tuesday 3/27/12
  
• Prove via induction that the sum of the first n integers is equal to n(n+1)/2 - due Tuesday 3/27/12
• In addition to computing (a mod b), also output/display: a / b. For example: 42 / 11 ==> 3 (and 42 mod 11 ==> 9)
  Compute the product of two input card values: A x B ==> ? - due Thursday 3/22/12
• Write a Simple Computer program to read in three values from the input. For each value, double it and write it to the output. Your program must use a loop. The value "3" should be assumed to already be in cell 10. (You'll have to put it there yourself.) - due Tuesday 3/20/12
• Given the 1-bit adder developed in class, compute the number of transistors used in a 32-bit adder.
  Show, using only NAND gates, how to construct an "AND" circuit, and "OR" circuit and a "NOT" circuit.
  Show, using only NOR gates, how to construct an "AND" circuit, and "OR" circuit and a "NOT" circuit. - due Thursday 2/23/12
• Update windowCloser.py so that the room does not have to be a rectangle - due Tuesday 2/7/12.
• Update babySaver2.py so that the "baby" can be anywhere along 1st Street. (i.e. Not only in the lower right corner of an obstacle.) - due Tuesday 2/7/12.

Software Environments

• JES - Download and Install. This is our Media Computation tool.
  A listing of the relevant JES Commands.
  • JES for Mac
  • JES for Windows (w/Java)
  • JES for Windows (w/out Java)
  • Media Sources Everyone should download this folder - contains lots of photos
    
  
  
• The Simple Computer
  
  • If the primary Simple Computer link is unavailable, try this alternative local link
  • Here is a short summary of the Simple Computer Instruction Set,
  • Some example programs.
    
  
  
• Alternative Karel World Builder: For those Windows users for whom the supplied world builder does not work, there is an alternative Karel world builder. Right-click the link to save the file to your desktop. Simply double click the file: "KareKJRobot.jar" to invoke the world builder.
  Note: This is a java (jar file) program. You must have java installed on your machine for this to run.
  
  
• Monty Karel the Robot:
  Install Python on your home/personal computer, and downlowd and extract MontyKarel onto your computer/USB key drive. Here are the instructions for installing Python and MontyKarel on your computer (or how to find Python on a public lab machine). Try running the included program firstKarelPgm.py -- found in the MontyKarel folder to test the installation.
  
  
• Scratch:
  Install Scratch on your home/personal computer. Simply visit the Scratch Website and following the download/installation instructions found there.

Examinations:

• The mid-semester examination is tentatively scheduled for Thursday March 1, 2012.
  • A Study Guide for you to peruse.
  
  
• The final (cumulative) examination is will be administered on Tuesday May 1, 2012 (4:00-5:50).
  • A Study Guide for you to peruse.