Course Information

• Instructor: Professor Çetin Kaya Koç         → Koç is pronounced as "Coach"  

• Class Schedule: Tue 3:30-6:00pm, HFH 1132
• Instructor's Office Hours: Mon, Wed 3:30-5:00pm
• Instructor's Office: HFH 1119

• Teaching Assistant: Han-Wei 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

• The grades: cs192Fall2016.htm   (The Code is your PERM number mod 9973)   ←

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 2-4 pages of Project Paper or 12-20 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

• Write-Once Erase-Never Memory
• Very-Long-Term Memory Devices
• Computing Pi: pi
• Arbitrary precision floating-point 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 d-dimensional 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: 7-bit and 8-bit ASCII, Unicode, UTF-8, 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, Church-Turing 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; carry-propagate, carry-save, and carry-lookahead 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, Runge-Kutta, pitfalls of numerical computation: Hilbert matrix, Wilkinson polynomial.
• Numerical and Symbolic Computation and Tools
  Matlab, R, and Mathematica.
• Parallelism
  Circuit-level 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

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ç

• https://koclab.net/koc.html
• E-mail:
• Tel: (805) 893 7426
• Office: HFH 1119