CMPS 13H: Honors Introduction to Programming and Data Structures
Winter 2004

Prof. Scott A. Brandt

Computer Science Department
University of California, Santa Cruz


NEWS:

 

3/10/04 - Final review slides are available here. Please keep in mind that the final will cover everything we did in class, except those things I mentioned would not be included in class today.

3/3/04 - Assignment 8 will be to implement the tree mover from this. Don't compute the fewest number of moves, but do output the number of moves your program makes. Try to make your program efficient. Anybody who implements a correct program that runs faster than my n+1 moves program will get extra credit. And, you may turn the assignment any time before the final exam. However, I would like to suggest that you don't wait so long that you don't have time to study for the final exam.

2/27/04 - Assignment 7
You have a choice:
1. Assignment 4 from 12B, or
2. Problem F from the 2003 ACM Programming Contest. Don't actually solve the problem, just build a quad tree representation of the image. Then, from the quad tree, build the actual image. If possible, meaning everything from here on is extra credit, display it. Also, if possible, create some random nxn images, where n is a power of 2, and create the quad tree representation of them. Then, if you're really motivated (bored), you could make your quad tree representation lossy, by encoding a region as all the same if it is X% the same. X can be a parameter. Play with it and see what you get. Also, if you are really bored, I mean motivated, you could try displaying your images before and after compression.

2/27/04 - Some sample exams:

  • A 12A Final
  • A 12B Final
  • The last 13H Final

    2/20/04 - The revised sorting code is available - here. It demonstrates how to do sorting with a linked list, which is insanely slow, and sorting with a binary search tree, which is reasonably fast and very flexible. Note that is requires that you have the binarysearchtree, binarytree, linkedlist, and queue directories (from BinaryTree.zip). You will also want the Doubly Linked List code.

    2/19/04 - The binary search tree code - is available in the java directory, in the BinaryTree subdirectory. Alternatively, a zipped file is available here.

    2/13/04 - Sorting code is available - here.

    2/9/04 - Sample code from class today: and all other sample code is available here.

    2/4/04 - Sample code from class today:

  • Makefile
  • Stack.java
  • UseStack.java

    2/2/04 - The solution for Assignment 2 is now available on the assignments page. Assignment 3 will be posted soon.

    2/2/04 - Linked List code: LinkedList.java and UseLinkedList.java.

    1/28/04 - Example code for the Complex class - is available here, and the program that uses it is here. And the polynomial code is here.

    1/16/04 - The Tic-Tac-Toe code from class today - is available here. Feel free to use it.

    1/15/04 - Office hours today - My office hours today will be from 3:00 to 3:45 and I will have no office hours on 1/22/04 (I will be out of town). To make up for this, I am adding office hours on Tuesday next week from 9:00 to 11:00 am.

    1/14/04 - New Location - After today, we will be meeting in Soc Sci 2, Room 159.

    1/12/04 - The class schedule - The class schedule below is now complete and correct. The other pages will be updated soon to reflect these dates.

    1/9/04 - Tio - To get tio to work properly, you need a tio directory in the same directory as your java code. In that directory there should be the .java and .class files for the tio archive. You can get all of it here in zip format.



  • Time: MWF 3:30-4:40
    Location: Soc Sci 2, Room 159
    Instructor: Prof. Scott A. Brandt (sbrandt@cs.ucsc.edu)
    Office/Office Hours: BE 251 / Th 3:00-5:00
    TA: Rajya Hari (rhari@soe.ucsc.edu)
    TA Office/Office Hours: TBD
    Lab Hours: BE 105 / W 12:00-2:00
    Prerequisites: Instructor permission
    Required Text (1): Java by Dissection, by Pohl and McDowell
    Required Text (2): Data Abstraction and Problem Solving with JAVA, by Carrano and Prichard
    Supplemental Text (1): C for Java Programmers, by Müldner
    Supplemental Text (2): A Practical Guide to the Unix System, by Sobell
    Supplemental Text (3): The Java Tutorial, http://java.sun.com/docs/books/tutorial/index.html
    Course Web Page: http://www.cs.ucsc.edu/~sbrandt/13H
    Class Newsgroup: ucsc.class.cmps013h

    Course Objectives

    This course presents an honors-level introduction to programming and data structures including the fundamentals of java programming and basic data structures such as linked lists, queues, trees, hashing, and computational complexity. It combines the material covered in CMPS 12A and CMPS 12B into a single quarter providing a fast-paced introduction to this material for outstanding students who have some prior programming experience but are not necessarily ready to take CMPS 12B.


    Grading

  • There will be bi-weekly homework assignments worth a total of 10% of your grade.
  • There will be weekly programming assignments worth a total of 40% of your grade.
  • There will be a comprehensive final exam worth 50% of your grade.

    Note: An average of less than 50% on the assignments or the final exam will result in a failing grade regardless of the overall average.


    Homework

    Homeworks will be questions taken from the books and are intended to make sure that everyone is doing the reading and to test your understanding of the material from each chapter. Homeworks will be graded on a simple three point scale: 0 = unsatisfactory (less than 50% attempted or correct), 1 = satisfactory (full credit), and 2 = outstanding (extra credit).


    Programming Assignments

    The programming assignments are an important component of the course.

    One thing to remember: your assignments must work in the environment on the CATS system. You can create your programs anywhere you want, but they must work on our system to get full credit.

    Due dates and lateness:

  • Homeworks and programming assignments are due on the date and time specified.
  • Late homeworks and programming assignments will not be accepted except when due to true emergencies.
  • Graded homeworks and programming assignments will be returned as soon as possible, usually within one week.


    Attendance

    Class attendance is mandatory. I will post homeworks, assignments, and important dates on the class web page, but this is provided as a courtesy and is not always complete. It is your fault if you miss something important because you skipped class.

    Lab attendance is also required. You will miss important material if you do not attend.

    Office hours are optional. They are your chance to ask the professor and the TAs questions about the material being covered, the programming assignments, etc.


    Academic Honesty: Collaboration vs. Cheating

    This really should not be an issue, but recurring events have made the following necessary.

    You are encouraged to discuss the course material and concepts with other students in the class. However, all work that you submit must be your own. Under no circumstances may you look at anyone else's code or show anyone else your code. And while you may discuss the concepts used in the programming assignments, you may not discuss implementation details of the assignments themselves.

    If you are caught copying or otherwise turning in work that is not solely your own, you will fail the course and a letter will be sent to your Department, the School of Engineering, and to your Provost and academic preceptor.

    The bottom line is that you are expected to conduct yourself as a person of integrity - you are expected to adhere to the highest standards of academic integrity. This means that plagiarism[1] in any form is completely unacceptable. As a (soon to be) computing professional, I encourage you to consult the code of ethics appropriate to your discipline[2]. You should also read the University Policy on Academic Integrity.

    Plagiarism will be assumed until disproved on work that is essentially the same as that of other students. This includes identically incorrect, off-the-wall, and highly unusual duplicate answers where the probability of a sheer coincidence is extremely unlikely. All parties to this unacceptable collaboration will receive the same treatment.

    You should bring a picture identification with you to all examinations and be prepared to show it upon request.

    If you are unsure of what is and is not allowed by this policy, talk to the instructor.

    1 pla-gia-rize vt. to steal and pass of as one's own (the ideas or words of another) to present as one's own an idea or product derived from an existing source - pla-gia-riz-er n. (source: Webster's New World Dictionary).
    2 The Association for Computing Machinery is http://www.acm.org/, the IEEE is http://www.ieee.org/ and the IEEE Computer Society is http://www.computer.org/.


    Getting Answers to your Questions

  • Attend class and labs
  • Check the class web page frequently - I will post as much information as I can
  • Read the class newsgroup: ucsc.class.cmps13h
  • Meet with the professor and TAs during office hours
  • Email the professor and TAs
  • Do not drop by or call on the phone outside of office hours


    Class Schedule

    This is a loose schedule for the class. This page lists all assignments, due dates, and reading material by date. This schedule is tentative, and will almost definitely be adjusted periodically to reflect how far we've gotten in class. In other words: This schedule is subject to change through the quarter. Assignment dates and due dates may be modified depending on the pace of the class.


    Day
    Date
    Topics
    Read before class
    Week 1:
    M
    Jan. 5
    Class Introduction
    Java Introduction
     JBD, Ch.1
    W
    Jan. 7

    Java Introduction & Program Fundamentals

     JBD, Ch. 1 & 2
    F
    Jan. 9
    Program Fundamentals
     JBD, Ch. 2
    Su
    Jan. 11
    Assignment 1
    Week 2:
    M
    Jan. 12
    Statements and Control Flow  JBD, Ch. 3
    W
    Jan. 14
    Statements and Control Flow & Functional Abstraction  JBD, Ch. 3 & 4
    F
    Jan. 16
    Functional Abstraction
     JBD, Ch. 4
    F
    Jan. 16
    Homework 1
    Su
    Jan. 18
    Assignment 2
    Week 3:
    M
    Jan. 19
    School Holiday
    W
    Jan. 21

    Arrays

     JBD, Ch. 5
    F
    Jan. 23
    Arrays & Data Abstraction  JBD, Ch. 5 & 6
    Week 4:
    M
    Jan. 26
    Data Abstraction
     JBD, Ch. 6
    W
    Jan. 28
    Intro to Data Structures
     DA&PS, Ch. 3
    W
    Jan. 28
    Assignment 3
    F
    Jan. 30
    Intro to Data Structures & Linked Lists
     DA&PS, Ch. 3 & 4
    F
    Jan. 30
    Homework 2
    Week 5:
    M
    Feb. 2
    Linked Lists  DA&PS, Ch. 4
    W
    Feb. 4
    Stacks
     DA&PS, Ch. 6
    F
    Feb. 6
    Stacks & Queues
     DA&PS, Ch. 6 & 7
    Su
    Feb. 8
    Assignment 4
    Week 6:
    M
    Feb. 9

    Queues

     DA&PS, Ch. 7
    W
    Feb. 11
    Algorithm Efficiency & Sorting
     DA&PS, Ch. 9
    F
    Feb. 13
    Algorithm Efficiency & Sorting
     DA&PS, Ch. 9
    F
    Feb. 13
    Homework 3
    Week 7:
    M
    Feb. 16
    School Holiday
    M
    Feb. 16
    Assignment 5
    W
    Feb. 18
    Algorithm Efficiency & Sorting
     DA&PS, Ch. 9
    F
    Feb. 20
    Trees
     DA&PS, Ch. 10
    Week 8:
    M
    Feb. 23
    Trees  DA&PS, Ch. 10
    W
    Feb. 25
    Trees
      DA&PS, Ch. 10
    W
    Feb. 25
    Assignment6
    F
    Feb. 27
    Tables & Priority Queues
     DA&PS, Ch. 11
    F
    Feb. 27
    Homework 4
    Week 9:
    M
    Mar. 1
    Tables & Priority Queues
     DA&PS, Ch. 11
    W
    Mar. 3
    Tables & Priority Queues
     DA&PS, Ch. 11
    F
    Mar. 5
    Advanced Tables
    DA&PS, Ch. 12
    Su
    Mar. 7
    Assignment 7
    Week 10:
    M
    Mar. 8
    Advanced Tables
    DA&PS, Ch. 12
    W
    Mar. 10
    Advanced Tables DA&PS, Ch. 12
    F
    Mar. 12
    Review
     
    F
    Mar. 12
    Homework 5
    Su
    Mar. 14
    Assignment 8
    Th
    Mar. 18
    FINAL EXAM: 12:00 - 3:00 in the usual classroom


    Telephone: (831) 459-5042 / FAX: (831) 459-4829 / sbrandt@cs.ucsc.edu