IT310 Java Support Site

Today is: 2024-11-20 | Current Unit: 02

  Due: 03-13-2013
e Newsletter
A newsletter published by http://java.skillbuilderblocks.com to help students succeed!
Course: IT310 Data Structures and Algorithms | Vol: 1301C | Issue: 2 | Date: 2013-03-07


From the Prof  FAQs

Greetings Class!

If you have taken a sneak preview at your reading assignment for this week, you already know that it's a DOOZY (I suspect it is for most of you anyway)! Please don't let it scare you and know that you don't have to do any math (leave that to the mathematicians - for now anyway). Your primary focus in this class needs to be on writing compilable code.

Of course you do need to understand the underlying point to doing complexity analysis and its importance when the projects you develop must handle large volumes of data. For now, let me simplify it to provide you with a sufficient foundation so you can move forward.

In a nutshell, typically there are many ways to solve a given problem, some more efficient than others. In the context of algorithms, two factors impact a program's performance: 1) time and 2) space. Time refers to the time it takes to perform the indicated steps, and space may be either space in RAM or disk space. If a program takes excessively long, or locks up due to lack of space, it will never be adopted by users (and can be quite embarrassing). For our purposes we're concerned only with time complexity for this unit (number of steps involved).

Consider an algorithm that all of you learned in grade school, namely basic multiplication, though you may not think of it as an algorithm. The greater the number of digits in the problem, the greater the number of steps it requires, and thus, the longer it takes to solve:

6
x  3
18
12
x  12
24
120
144
115
x  145
575
4600
11500
16675

Now, assuming you memorized your multiplication tables like the dutiful student you were back then and didn't have to rely on fingers and toes, theoretically the second calculation took approximately 5 times longer to do than the first (including the addition) while the third calculation took approximately 10 times longer.

In terms of bits and bytes, time complexity is not just about math and applies equally to other characters and symbols (though the computer interprets them numerically). For example, the word "A" is 8 bits or 1 byte, while the word "antidisestablishmentarianism" consists of about 28 times more data and would take a correspondingly longer amount of time to process (note these times are not mathematically precise, but rather approximations).

While algorithms are generally designed to work with inputs of varying length, they also commonly must process entire data sets (e.g. arrays) and have special functionality (i.e. search, sort, loop, make decisions, etc). These conditions typically add to the time complexity by significantly increasing the growth rate and thus the resource requirements. They are also dependent on the power and efficiency of the platform on which they run. For all of these reasons, you should make it a point to familiarize yourself with typical use cases and the common algorithms that can handle the needs of your programs and use those that are best-suited to those needs.

Please see the FAQs and other resources on the support site for more!

Warm Regards,
Kathy

 

Q: What is Big-Oh?
A: In the context of algorithm analysis, you can think of big-oh (O) as the order of magnitude. Put simply, O refers to the smallest upper bound that a function will grow. Though not a complete list, common time complexities are stated as:

  • O(1) - time is constant (no growth or number of operations is 1 regardless the value of n)
  • O(n) - time is linear (grows with n when n doubles)
    • n = 1, number of operations = 1
    • n = 2, number of operations = 2
    • n = 4, number of operations = 4
  • O(n2) - time is quadratic (grows twice as fast as n when n doubles)
    • n = 1, number of operations = 1
    • n = 2, number of operations = 4
    • n = 4, number of operations = 16
  • O(n3) - time is cubic (grows three times as fast as n when n doubles)
    • n = 1, number of operations = 1
    • n = 2, number of operations = 8
    • n = 4, number of operations = 64

Q: What are common Java functions (algorithms) and their time complexity stated in Big-Oh?
A: Again an incomplete list, but some basic ones to get your started are:

  • Loop that counts up to or down to n - O(n) or linear
  • Linear search of an array, ArrayList, or LinkedList - O(n) or linear
  • Search a hash table - O(1) or constant
  • BubbleSort - O(n) or linear
  • Selection Sort - O(n2) or quadratic

Q: What are common symbols used in algorithmic analysis?
A: Common symbols used in algorithmic analysis (besides O discussed above) include:

  • Θ = theta (used to restrict the possible Ω lower bounds and O upper bounds)
  • Ω = omega (big-omega refers to the largest lower bound of a function)
  • Σ = sigma (sum)
  • ms = millisecond (1/1000 of a second)
  • µs or µsec = microsecond (1 millionth of a second)
  • ns = nanosecond (1 billionth of a second)
  • ∞ = infinity

Q: When is Unit 2 due?
A: 03-13-2013

Q: How can I get help?
A: You have several options depending on what you need help with as follows:

  1. Go to the Java Support Site. There you will find:
    • Links to the weekly announcements, including newsletters and seminar recordings
    • Seminar agendas
    • Project demos and sample code
    • Tutorials
    • Help Ticket Application - use to get my help troubleshooting your code
  2. Join me for office hours
  3. Post course related questions in the Virtual Office (I look there first and frequently)
  4. For issues of a more personal nature, use email
  5. If this isn't enough, check out Kaplan's Technology Center for tutoring options!
     

The seminar recording covering the following topics is here http://khe2.adobeconnect.com/p1f34ski7m7/

  • What is an algorithm?
    • A precise description of the steps needed in a computation that produces a solution to a problem
    • The sequence of instructions within a program that implements a processing operation
    • A problem-solving procedure that uses comparison and branching functions
  • Algorithmic complexity analysis
    • Review newsletter for scope
  • The differences between the best, worst, and average case for an algorithm
    • Best case is when the algorithm can do the job in the fewest number of steps
    • Worst case is when the algorithm does the job in the greatest number of steps
    • Average case falls between best and worst, but is problematic because you would have to know all possibilities and probabilities to determine average
    • Example: A sequential search of an unordered array finds the value in the first cell (best case); it finds the value in the last cell or not at all (worst case); Calculating average
  • An efficient algorithm
    • Generally speaking a program with the best running time is a better one
    • For programs that run only once or a few times and are no longer needed, any algorithm will do except for exponential (quadratic, cubic, etc) - they may never finish
  • This week's goal - demo (see project instructions for more details)
    • Modify Time.java by adding methods for n^2 and 2^n and functions that output the results.
    • Run the program
    • Copy and paste the outputted data into Excel. Graph the time data and modify the graph as needed.
    • Save the Excel file in the unit02 folder, zip it and attach it to the dropbox.
  Due: 03-13-2013

PROJECT INSTRUCTIONS


Calculate Squares, Exponentials, Run Times and Graph the Time Results

  1. Download Time.java from Doc Sharing and save it in a folder named unit02
  2. Create a new project in your IDE named unit02. Choose java project with existing sources. Include the folder containing the Time.java file
  3. Modify the timing program by adding two methods, one called squared that calculates and prints n2, and one called exponential that calculates and prints 2n
  4. Compile and run the project
  5. Copy and paste the output into Excel (use text to columns if necessary to make the data graphable)
  6. Graph the time for each execution of the square and exponential loops
  7. Modify the graph to make the data readable if necessary
  8. Save the Excel file as unit02.xlsx in your unit02 compiled project folder
  9. Zip the unit02 project folder and attach the zip to the dropbox

PROJECT DEMO


SCREEN SHOT OF NETBEANS OUTPUT

unit02a.gif

SCREEN SHOT OF EXCEL DATA AND GRAPH

unit02b.gif

Still not enough time! Hopefully sooner than later.