CS 192 Projects in Computer Science (Computational Thinking)
Fall 2016  EnrlCd: 61671  Credits: 2
Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/cs192
Course Information
 Instructor: Professor Çetin Kaya Koç
→ Koç is pronounced as "Coach"
 Class Schedule: Tue 3:306:00pm, HFH 1132
 Instructor's Office Hours: Mon, Wed 3:305:00pm
 Instructor's Office: HFH 1119
 Teaching Assistant: HanWei Kung (hkung@umail.ucsb.edu)
 Teaching Assistant Office Hours: TBA
 TA Office: Trailer
936 Room 104
 Please join the
Piazza page
for class discussions ←
 Check the class website and the Piazza page once a day
 Slides and course notes are in the folder
docx
 Homework and Projects documents are in the folder
hwpro
Homework Assignments and Project
 There will be 3 Homework Assignments and one Project
 Homework Assignment 1: hw1.pdf
due 9pm, Tue Oct 25
 Homework Assignment 2: hw2.pdf
due 9pm, Tue Nov 8
 Homework Assignment 3: hw3.pdf
due 9pm, Tue Nov 29
Dropbox
Link for hw3
 Project Requirements: Submit 24 pages of Project Paper or
1220 pages of Project Slides. No need to submit programs; submit only
the description or the results. Deadline: 9pm Monday December 5
Dropbox
Link for Project Submission
Project Ideas
 WriteOnce EraseNever Memory
 VeryLongTerm Memory Devices
 Computing Pi: pi
 Arbitrary precision floatingpoint arithmetic:
mpmath
 IEEE 754 Library: ieee754
 Noto Project: noto
 Efficiency of image compression: gif, jpg, png
 Watermarking images with text, image, music
 Audio representation and processing
 Fractals: Find new recursively generated fractals
 Implement the ddimensional Hill cryptosystem
(Key Generate, Encryption, and Decryption functions)
Course Topics

Data Representation and an Overview of Computing
What is information? How do we represent data?
History of numbers and calculation,
Leibniz’s system of 0’s and 1’s, analog versus digital data.

Representation of Text
Representation of numbers, binary, decimal, and hexadecimal
number systems, representation of simple text and structured
text; text encoding: 7bit and 8bit ASCII, Unicode, UTF8, etc.

Representation of Images and Video
Representing images, intensity, pixels, tradeoffs in
representation, data formats, headers, compression algorithms,
optimization, Huffman coding.

Representation of Sound and Music
Representation of data other than text, analog sound,
digital sound, sampling, digitized music, distortion,
sound compression and decompression.

Iteration
Iterative computations of sums, products, and sums of products,
or products of sums. Computation of constants such pi or e.

Recursion
Types of recursion, recursive algorithmic paradigms, numerical
examples, complexity estimates.

Universal Computation
What is universality? The Turing machine model, ChurchTuring
thesis, time/space, determinism/nondeterminism.
When is a problem more difficult than another? Simulations,
hierarchies of problems, limits of computation, decidability,
completeness.

Arithmetic Algorithms
Addition of integers; carrypropagate, carrysave, and
carrylookahead adders; multiplication, multiplication by
shift and add, simple recursive algorithms, Karatsuba algorithm.

Advanced Algorithms
Linear programming, dynamic programming, and Fast Fourier Transformation.

Searching and Sorting
Ordering data, data structures, linear search, binary search,
heap, binary tree; Sorting by searching for minimum,
Bubble Sort, Quicksort, Mergesort, selection.

Analytical versus Numerical Computation
Solving differential equations using analytical methods, making
sense of the solutions; solving differential equations using
numerical methods: Euler, RungeKutta, pitfalls of numerical
computation: Hilbert matrix, Wilkinson polynomial.

Numerical and Symbolic Computation and Tools
Matlab, R, and Mathematica.

Parallelism
Circuitlevel parallelism, parallel computers, topology of
connections, sharing data among processors.

Everyday Cryptography
Confidentiality and authentication, how to keep your data away
from prying eyes, securing private information using encryption,
how to determine with whom we are talking on the Internet,
proving identity, digital signatures.
Grading Rules
 Homework Assignments: 45 %
 Project: 55 %
Catalog Specification
Projects in computer science for advanced undergraduate students.
Prerequisites
 Consent of instructor
 Letter grade only
 Students must have a minimum 3.0 GPA
 May be repeated to a maximum of 8 units with consent of
department chair
Academic
Integrity at UCSB ←
Dr. Çetin Kaya Koç
