Intro to computing. ITC. IBA Fall ‘23.

Arrival, the movie. Why introduction to computational thinking feels like an alien language to some students.

Pre-reads and resources by week for ITC / ICA (Intro to computing applications) students. IBA, Karachi, Spring 2023. Teachers, students and teaching assistant resources.

Why should you expect from ITC. The Orientation orientation.

Lectures and tutorial play list

Week I and II lectures and tutorials shared so far.

What is this course about?

There are two core computer science (CS) courses in the first semester at IBA for computer science majors. The first is introduction to programming (ITP). ITP is a hands-on language syntax and structure focused course that teaches students how to program.

Introduction to computing (ITC) is a complimentary course that focuses on the context around why? Why should we learn to program? Why is that a challenge? How is computational thinking different from conventional thought? How should we attack problems that we need to solve as computer scientists? What is the historical context around using machines, especially computational machines for problem solving? How do we use grammar and language to describe the nature of thought? What are the challenges associated with expressing and explaining solution design visually? Will we see inorganic intelligence arrive and arise in our lifetime? Isn’t it already here?

While ITP is a practice focused course, ITC explores the philosophy of thought within the context of CS. The programming course focuses on skills. The computing course on context. Together they help set the foundation for courses that follow in the next four years of your education.

To add color to context, ITC uses two related themes to illustrate frameworks important to computer science. Artificial intelligence (AI) and a sub field, Game AI. Cases, models, and illustrations use these themes so students contribute to intelligent conversations and get exposed to two trends that will play a key role in our markets.

Our objective is to provide a broad introduction to the field in 14 weeks. Hence treatment of multiple topics is limited to a simplified introduction. The idea is to get students to think about core questions and choices early on in their education so that they can make informed decisions about careers and related course selections. And guide them to resources they can use for deeper dives. In some instances, there is thematic overlap with ITP but the nature of coverage and treatment between the two courses is different.

Why AI and Game AI?

How do we engage students who feel they have done all the groundwork required for the course? Introduce them to applications of mathematical expressions and data structures early in the course.

There are three key data structures we introduce: arrays, linked lists, and trees. Decision trees, state diagrams and transition tables translate very easily to the game AI world without getting into complex discussions on mathematical expression, discrete mathematics, programming syntax or automata.

Game AI using decision trees makes it possible to run interactive fun classes that delve into the nature of intelligence without prior high-level math or programming background. The idea is to develop a mindset for problem solving by working through simplified use cases. Since most students have some exposure to gaming, we assume this area of inquiry would be of interest to them and would lead to better participation and engagement on their behalf. As a current topic of discussion, it will also help keep the course relevant and applicable to professional growth and development.

Reference points and benchmarks.

Take a look at how UVA does it at — https://computingfor.github.io

Week One. Thinking.

Computational Thinking topics and objectives

Teacher’s Resources:

1. AlphaGo (Documentary)
2. “Genius Makers: The Mavericks Who Brought AI to Google, Facebook and the World” book by Cade Metz
3. “Chip Wars” book by Chris Miller

Student and TA’s Resources. Required readings for assessment.

1. Design is. https://medium.com/design-your-life/5b867e9f2614
2. Comparing genomes and operating systems in terms of the topology and evolution of regulatory control networks. (Will be tested on this). https://www.pnas.org/doi/full/10.1073/pnas.0914771107
3. Design is not… (Will be tested on this). https://medium.com/user-experience-design-1/design-is-not-science-art-or-engineering-5e8d2f499494

Recommended readings.

1. Professor Wing’s presentation on computational thinking. https://www.cs.cmu.edu/afs/cs/usr/wing/www/talks/ct-and-tc-long.pdf
2. Computational thinking for everyone. Professor Wing. https://www.researchgate.net/publication/23142610_Computational_thinking_and_thinking_about_computing
3. Computational thinking is more about thinking. https://link.springer.com/content/pdf/10.1007/s41979-020-00030-2.pdf?pdf=button
4. How to outperform a 10x developer. https://betterprogramming.pub/how-to-outperform-a-10x-developer-fa1132807934
5. Design is not… Part II (Will be tested on this). https://medium.com/user-experience-design-1/design-is-not-a-science-49c35bfcc14b
6. For context on 10x programmers, see:

Week Two. Scrabble.

Teacher’s Resources:

1. https://writings.stephenwolfram.com/2023/02/what-is-chatgpt-doing-and-why-does-it-work/

Student and TA’s Resources. Required readings for assessment.

Scrabble online game
https://playscrabble.com/

1. Checkers online game
   https://www.247checkers.com/
2. “The World’s Fastest Scrabble Program” by Andrew W. Appel and Guy J. Jacobson https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf
3. Interaction design. https://medium.com/user-experience-design-1/interaction-design-is-more-than-just-user-flows-and-clicks-4cc37011418c
4. Graph and Tree data Structures. Optional reading.
   https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8

Building the Scrabble AI resources

1. Wordsmith by Scott Young. https://www.scotthyoung.com/blog/2013/02/21/wordsmith/
2. The World’s fastest Scrabble Program, video explanation and representation. https://youtu.be/d07ntA9W7YE?si=hM6EHBbW4OoYlNTQ
3. Building the world fastest Scrabble….https://medium.com/@aydinschwa/coding-the-worlds-fastest-scrabble-program-in-python-2aa09db670e3
4. Scrabble is nowhere close to being a solved game, https://medium.com/@14domino/scrabble-is-nowhere-close-to-a-solved-game-6628ec9f5ab0

Week Three Readings. Excel. Pivot Tables. BI.

This set of reading provide background and context for the two BI datasets we will use in the two /three week BI component of this course.

1. The I in BI…https://risktrainer.medium.com/the-i-in-bi-7399af34113d
2. Tracking Growth. https://risktrainer.medium.com/tracking-growth-a-case-study-ea81760368be
3. Sizing markets. https://risktrainer.medium.com/sizing-markets-5582ef58484b

Week Four. Review. Assessment

1. The first two week in ITC. Scrabble, Search Spaces, Board Evaluation. Memory. https://risktrainer.medium.com/search-spaces-scrabble-board-evaluation-memory-2f99eaa944a3
2. ITC Pre-release for Week III assessment. https://risktrainer.medium.com/itc-pre-release-for-week-iii-quiz-68d03f70132a

Week Five Readings. Efficiency. Part I. Representation

1. Finite State Machines. Regular Expression. Grammar. MIT, OCW.

2. Directed Acyclic Graphs. https://medium.com/basecs/spinning-around-in-cycles-with-directed-acyclic-graphs-a233496d4688

3. Sorting out with Sorts. https://medium.com/basecs/sorting-out-the-basics-behind-sorting-algorithms-b0a032873add

5. DFA Minimization. https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm

Week Five. Assignment.

With this (aa, ab, abrupt, abide, abode, abstain, attempt, around, align, advantage, attempt, attitude, altitude, arraign, arrive, arrival, astride, assumption, ax, axe, axle, azure, ay, awe), a list of words beginning with a, do this (see the next two images).

The assignment can be attempted on any letter of the alphabet in the Oxford Word list, other than letters that have less than 50 words.

Think about this for a second. Efficiency through internal representation. Compare these two models with the crude word generation and validation approach we started our course with. The trie is clearly more efficient than brute force word generation. But the DAWG is even more efficient than a trie.

Build a Trie. 112 nodes.

Build a DAWG. 52 nodes

Week Six Readings. Big O and Time Complexity.

1. Understanding Big O. https://medium.com/yasser-dev/understanding-big-o-time-complexity-of-algorithm-in-7-mins-for-beginners-adbe5599d64c
2. Recursion vs Dynamic Programming. Fibonacci Numbers. https://towardsdatascience.com/dynamic-programming-i-python-8b20387870f5

Advance topics. Reference materials.

1. Build a DAWG. Building a Complete Inverted file for a set of text files in linear time. https://www.cs.colostate.edu/pubserv/pubs/Blumer-rmm-invertedFilesSTOC.pdf
2. 4. Building DAWGs. https://hal.science/hal-00620006/document

Efficiency. The search for log of n.

Week Seven. Mid Term Prep.

Watch this space for sample problems, test sets, advise and guidance.

Big Oh Notation. I and II

Advance Topics. (Won’t be tested. For advance readers)

Matrix Multiplication.

Bently Rules.

Week Eight. Performance. Sizing. Hardware.

1. There is plenty of room at the top. https://www.science.org/doi/epdf/10.1126/science.aam9744
2. Performance analysis. https://www.infoq.com/articles/arm-vs-x86-cloud-performance/
3. Comparing CPU. https://medium.com/@joecharp89/guide-to-comparing-cpus-for-your-pc-build-battlenubs-bytesized-blog-cb6546b571a8
4. Arm vs x86. One. https://medium.com/24sevenoffice-tech-blog/arm-vs-x86-lambda-performance-716fd1cabe26
5. Arm vs x86. Two. https://engineering.carsguide.com.au/arm-versus-x86-for-database-server-comparison-review-8911d3c582e9
6. Application specific architecture and hardware. https://arxiv.org/ftp/arxiv/papers/1911/1911.05289.pdf
7. Server sizing. https://financetrainingcourse.com/education/2014/10/estimating-traffic-visitors-aws-ec2-medium-servers-can-support/

Week 9. Digital logic circuits

1. Comparing two binary numbers. https://www.geeksforgeeks.org/magnitude-comparator-in-digital-logic/
2. Memory and multiplexers. https://medium.com/@kamil2000budaqov/logic-gates-to-computer-memory-659d7f90d4

Week 10–14. Final assessment. 8 bit CPU.

Build an 8 bit CPU using Logisim Evolution 3.8.

Restrictions

To be built, demonstrated on Logisim Evolution 3.8.0 (x86). You are allowed to use default Logisim registers and memory circuits, wiring, LED and splitters. You are not allowed the usage of tunnels, built in adders, decoders, multiplexers or controllers.

All components have to be built from the ground up. Collaboration is allowed and encouraged. However your viva will be on an individual basis. Irrespective of who did the work, you will have to defend all aspects of it.

Submission deadline. 8th December 2023.
Viva slots. In person. 9th and 10th December 2023. Main campus.

You have a choice of two different viva modes. The straight and easy path. The hard and difficult path. Please pick your path carefully. Your viva will focus on your ability to explain work you have done, level of understanding and awareness of principles and tools you worked with and your ability to extend frameworks to generalized situations you had not seen earlier in this course.

Please test your work and circuits. On the morning of the day of your viva you will receive a test script that will include a certain number of instructions in assembly language for the Dawit Design and instruction set. If you have used a different design then it is recommended that you convert the test instructions to your instruction set architecture. And test it on your circuit to ensure you produce the desired results.

A large part of your grade will be determined by your ability to successfully execute this test script and explain the sequence of execution that follows from it.

Resources

The Dawit play list. No sound, but very detailed, relatively modern design. Recommended and preferred. Historically speaking, despite the absence of sound, the Dawit playlist is easier to follow and leads to a workable, shippable design. You don’t have to follow the exact instruction set but the design principles laid our here are easily extended to the design requirements of your submission.

Alternate. The Ross Macgowan design and playlist. Has sound but quite a few students run into struggles in the more advance stages of design. You can ideally look at both and decide which one you like and prefer to follow.

As long as you understand what you are doing you are allowed to use either of the two, a mix of the two or a design of your own making as long as you understand how to translate your final design and instruction set architecture to the Dawit instruction set.

Readings for week 10–14.

1. Decoding Instruction sets — https://medium.com/@g.c.dassanayake/an-introduction-to-intel-32-bit-instruction-decoding-9b3b0c15bebb
2. https://medium.com/geekculture/digital-logic-series-1-boolean-algebra-and-logic-gates-5e81b4c0142b
3. https://medium.com/@kamil2000budaqov/logic-gates-to-computer-memory-659d7f90d4
4. https://www.electronics-tutorials.ws/category/boolean

Guidance

Build the calculating components first. 2 bits first. Then 4 bits using sub-circuits. Then 8 bits using sub-circuits again. Test and validate input, output, pins, logic. This is key. If you miss it, everything will fall apart. Then test and validate them together. This is also key.

Only put together tested and validated components.

You are not alone. Ask for help. Collaborate. Collate. Coordinate. Make sure you understand what you are doing. You have to understand why a circuit works the way it does. You have to understand how to change or modify or fix or debug or trace or test it. You have to understand how to extend it. You will also have to explain all the design choices you made. “I didn’t do this” isn’t a valid or acceptable answer.

Sample Test Scripts

0: 0f 1e 20 3f 0f 20 3f 00 00 00 00 00 1e 0f 00 1b

0: 0c 1d 20 3c 00 00 00 00 00 00 00 00 1e 0f 00 00

Final grade distribution. Fall ’23. Freshmen class.