Asymptotics and CS 101 Fundamentals of Computing Spring 2021: Difference between pages

From Computer Science at Indiana State University
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
wiki_previous>Jkinne
No edit summary
 
m 1 revision imported
 
Line 1: Line 1:
=Assignment=
== Catalog Description ==
Assignment for [[CS 303]].  Problems from [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Mathematics for Computer Science] (MCS).
The main focus of the course is to give students a practical understanding of computing to become well-informed citizens and professionals in the computing age.  Topics may include a basic study of - computational thinking, computer security, big data, artificial intelligence, and current trends in computing.


Note: for each question, give an explanation of why the answer is what it is. This does not need to be a formal proof. When possible you can use my big-O rules of thumb: (0) ignore constants multiplied out front, (1) for terms that are added just keep the fastest growing one (fastest eventually), (2) n<sup>c</sup> grows faster than (log(n))<sup>d</sup> for any constant c > 0 and constant d, (3) (1+c)<sup>n<sup>d</sup></sup> grows faster than n<sup>e</sup> for any constants c > 0, d > 0, and constant e.
== Prerequisites ==
Typing and basic computer use - web browser, email, etc.


# MCS Problem 14.20. Indicate whether each statement is true or not. Explain why for each. <br>''Note that for functions f(n) and g(n), the notation "f ~ g" means that the limit of f(n)/g(n) approaches 1 as n goes to infinity (this is like them being Theta of each other with a constant factor of 1); equivalently, for any constant epsilon>0 you can find a value n0 such that (1-epsilon) g(n) <= f(n) <= (1+epsilon g(n) for all n >= n0.''<br>''Note that sin(x) ranges between -1 and 1, and periodically goes between those two values forever; that is all you need to know about sin(x) for the one that has sin in the formula.''
== Standard Content ==
# MCS Problem 14.21. Show an asymptotic equation pertaining to factorial, using [https://en.wikipedia.org/wiki/Stirling%27s_approximation Stirling's formula].
===Course Outline ===
# MCS Problem 14.26. Arrange the functions in increasing big-O order. For some of these you also need to pay attention to the precise definition of big O.
We will spend 1-2 weeks on each of the following topics:
# MCS Problem 14.28. Determine which of the given options describes each function's asymptotic behavior. For part (e) you will need one of the summation formulas from here: https://en.wikipedia.org/wiki/Summation#Summation_index_in_exponents
* What is inside a computer: CPU, RAM, hard drive, etc.
# MCS Problem 14.33. For each pair of functions, find constants c and n0 that make the asymptotic formula true. The book asks for the smallest c, but you can find any c that satisfies the definitions. For each one, give some justification as well.
* Internet 101: how data is moved around the internet
* Computer and internet security: how do you know your data is secure?
* Servers and such: logging into a server, transferring files
* Html basics: creating web pages, a little bit of javascript
* Block programming: scratch.mit.edu, code.org, blocky
* Computational problems: things computers can do really well, and things that are impossible for computers to solve
* Artificial intelligence: different meanings of the term, examples


=Old assignment, from last term=
===Learning Outcomes===
The following are the most important learning outcomes for each of the 8 topics listed in the course outline.
* What is inside a computer
* Name the different components that make up a computer.
* Describe what the terminology associated with a component means (e.g., Ghz for CPU’s is the speed of the CPU, GB for the size of a hard drive).
* Evaluate the tradeoffs between different components (e.g., one CPU versus another)
* Internet 101
* Explain the basic infrastructure of the internet and associated terminology.
* Explain the infrastructure of a home network, and be able to configure a home network.
* Explain how web browsing and email works, in terms of which parties are involved (e.g., server and client), where data is stored, and what communication is involved.
* Computer and internet security
* Explain the concepts of encryption/decryption, digital signing, and the difference between public-key and private-key encryption.
* For given situations, be able to say whether a given interaction is secure or not.
* Know the key terminology of internet security (e.g., rsa, sha, https, etc.).
* Servers and such
* Explain what servers are used for
* Be able to log in to a server to transfer files to a server, and login via ssh to issue commands to the server
* How is data stored on a server, and how do we access data
* Html basics
* Explain the basic structure of an html document, and understand that an html document is a plain text file that has markup tags to say how to display different parts of the webpage.
* Be able to create simple html webpages.
* Be able to put webpages onto a web server.
* Block programming
* Understand the concept of a computer program as instructions for the computer.
* Be able to design simple programs in a graphical programming environment (one where there is no possibility for syntax errors, e.g., scratch).
* Computational problems
* Explain some examples of computational problems, and understand how problems are framed (input to the problem, correct output, running time of finding the solution).
* Basic skills in evaluating efficiency of an algorithm.
* Explain some examples of computational problems that either cannot be solved, or require inordinate amount of time to solve (e.g., halting problem).
* Artificial intelligence
* Understand the concept of the “Turing test” as a test of artificial intelligence.
* Know the history of some famous examples of “artificial intelligence” (e.g., chess playing, Jeopardy playing, chat-bots).
* Explain some examples of artificial intelligence techniques (e.g., spam filtering, facial recognition, expert medical systems).


# MCS Problem 14.18. Find the least non-negative integer n to make each statement true. Note that n=0 is theoretically a possible answer for some of these.
===Important Assignments and/or Exam Questions===
# MCS Problem 14.19. For each cell in the table, indicate whether the asymptotic statement is true or not. Note that for the ones that have sin, you have to pay attention to the precise definition of big O. For the one with n! you can use Sterling's approximation (any of the variations will be good enough).
* ''TODO''
# MCS Problem 14.25. Indicate which cells in the table are true. Note that for functions f(n) and g(n), the notation "f ~ g" means that the limit of f(n)/g(n) approaches 1 as n goes to infinity (this is like them being Theta of each other with a constant factor of 1). For the one with n! you can use Sterling's approximation.
 
# MCS Problem 14.26. Arrange the functions in increasing big-O order. For some of these you also need to pay attention to the precise definition of big O.
=== Standard resources ===
# MCS Problem 14.34. False claim, identify where it is incorrect.
* The Beauty and Joy of Computing - course on CS Principles, including programming in SNAP
* Computer Science Principles - a similar course by Amit Jain at Boise State with much of the content online
* Introduction to Computing - a similar course by Nick Parlante at Stanford with much of the content online
* HTML tutorial, CSS tutorial, More on CSS, Javascript tutorial
* Introduction to Computing: Explorations in Language, Logic, and Machines by David Evans
* A Computer Science Tapestry by Owen Astrachan
* Blown To Bits: Your Life, Liberty and Happiness After The Digital Explosion by Hal Abelson, Ken Leeden and Harry Lewis

Latest revision as of 13:22, 17 August 2025

Catalog Description

The main focus of the course is to give students a practical understanding of computing to become well-informed citizens and professionals in the computing age. Topics may include a basic study of - computational thinking, computer security, big data, artificial intelligence, and current trends in computing.

Prerequisites

Typing and basic computer use - web browser, email, etc.

Standard Content

Course Outline

We will spend 1-2 weeks on each of the following topics:

  • What is inside a computer: CPU, RAM, hard drive, etc.
  • Internet 101: how data is moved around the internet
  • Computer and internet security: how do you know your data is secure?
  • Servers and such: logging into a server, transferring files
  • Html basics: creating web pages, a little bit of javascript
  • Block programming: scratch.mit.edu, code.org, blocky
  • Computational problems: things computers can do really well, and things that are impossible for computers to solve
  • Artificial intelligence: different meanings of the term, examples

Learning Outcomes

The following are the most important learning outcomes for each of the 8 topics listed in the course outline.

  • What is inside a computer
  • Name the different components that make up a computer.
  • Describe what the terminology associated with a component means (e.g., Ghz for CPU’s is the speed of the CPU, GB for the size of a hard drive).
  • Evaluate the tradeoffs between different components (e.g., one CPU versus another)
  • Internet 101
  • Explain the basic infrastructure of the internet and associated terminology.
  • Explain the infrastructure of a home network, and be able to configure a home network.
  • Explain how web browsing and email works, in terms of which parties are involved (e.g., server and client), where data is stored, and what communication is involved.
  • Computer and internet security
  • Explain the concepts of encryption/decryption, digital signing, and the difference between public-key and private-key encryption.
  • For given situations, be able to say whether a given interaction is secure or not.
  • Know the key terminology of internet security (e.g., rsa, sha, https, etc.).
  • Servers and such
  • Explain what servers are used for
  • Be able to log in to a server to transfer files to a server, and login via ssh to issue commands to the server
  • How is data stored on a server, and how do we access data
  • Html basics
  • Explain the basic structure of an html document, and understand that an html document is a plain text file that has markup tags to say how to display different parts of the webpage.
  • Be able to create simple html webpages.
  • Be able to put webpages onto a web server.
  • Block programming
  • Understand the concept of a computer program as instructions for the computer.
  • Be able to design simple programs in a graphical programming environment (one where there is no possibility for syntax errors, e.g., scratch).
  • Computational problems
  • Explain some examples of computational problems, and understand how problems are framed (input to the problem, correct output, running time of finding the solution).
  • Basic skills in evaluating efficiency of an algorithm.
  • Explain some examples of computational problems that either cannot be solved, or require inordinate amount of time to solve (e.g., halting problem).
  • Artificial intelligence
  • Understand the concept of the “Turing test” as a test of artificial intelligence.
  • Know the history of some famous examples of “artificial intelligence” (e.g., chess playing, Jeopardy playing, chat-bots).
  • Explain some examples of artificial intelligence techniques (e.g., spam filtering, facial recognition, expert medical systems).

Important Assignments and/or Exam Questions

  • TODO

Standard resources

  • The Beauty and Joy of Computing - course on CS Principles, including programming in SNAP
  • Computer Science Principles - a similar course by Amit Jain at Boise State with much of the content online
  • Introduction to Computing - a similar course by Nick Parlante at Stanford with much of the content online
  • HTML tutorial, CSS tutorial, More on CSS, Javascript tutorial
  • Introduction to Computing: Explorations in Language, Logic, and Machines by David Evans
  • A Computer Science Tapestry by Owen Astrachan
  • Blown To Bits: Your Life, Liberty and Happiness After The Digital Explosion by Hal Abelson, Ken Leeden and Harry Lewis
Retrieved from "https://cs.indstate.edu/web/index.php?title=Asymptotics&oldid=25"