Applying euclid's algorithm for gcd 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
m 1 revision imported
 
m 1 revision imported
 
Line 1: Line 1:
[https://en.wikipedia.org/wiki/Euclidean_algorithm Euclid's algorithm] for the greatest common divisor is often among the first algorithms seen that has a significantly faster run time than the naive algorithm (exponentially faster, in fact).  A traditional assignment is to ask you to work through the application of Euclid's algorithm on a pair of integers that are modestly large.
== 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.


=Example=
== Prerequisites ==
Consider the integers 12345 and 67890.  We let a=67890, b=12345, and apply the Euclidian algorithm in the following steps.
Typing and basic computer use - web browser, email, etc.
* a = 5*b + 6165, so set a=12345 and b=6165
* a = 2*b + 15, so set a=6165 and b=15
* a = 441*b + 0, so gcd(a, b) = b
We conclude that gcd(67890, 12345) = 15.  Note that we could perform the divisions required by hand or used a calculator (or other means), but we have showed how we work through the algorithm until we have the gcd at the end (when we get a 0 remainder).


=Assignment=
== Standard Content ==
You will be assigned values of a and b and asked to work out the gcd in the same way as above.
===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


'''Pass rating check''' You should follow the same steps as above, and include a similar amount of text as above so that you have clearly stated what you are doing, and someone can verify that you have applied Euclid's gcd algorithm correctly.
===Learning Outcomes===
You need to ''both'' hand in your work, and also check in with the help lab to demonstrate the algorithm. You can use your work that you hand in, and should talk the GA through the algorithm. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process.
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).


''Note - the shared spreadsheet that GAs use for submitting information to Jeff Kinne's courses is [https://sycamoresindstate-my.sharepoint.com/:x:/g/personal/jeffrey_kinne_indstate_edu/ESbWO8QmBg9Jn9-ufDqR6_EBPzUbhzjVjyyzAPEAcjbMgg?e=XBpLEa this link], which should work only for the current term's GAs.''
===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

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=Applying_euclid%27s_algorithm_for_gcd&oldid=25"