Skip to main content

653.01 questions

Class 01 questions:

What does sorted mean?

How do you measure efficiency / the best?

How do you measure how much memory an algorithm requires?

How do you count the instructions an algorithm requires?

How do you define correctness?

Are there any other meaningful types of correctness than exactly, usually correct, and close to it?

How do you know if you have a match - you're done looping?
Is it possible that a looser definition for a match may speed up an algorithm?

What is a random algorithm?

What is a probabilistic algorithm?

The presumptive aspects to measuring speed are: machine, compiler, programmer, input size, input kind, and power. Are there any other meaningful properties?

How do we abstract machine, compiler, programmer, input size, input kind, and power?
Can we build a system that, with all properties abstracted, we can accurately measure/predict algorithmic space?
Can we infer a system that has certain properties and deduce the required machine/compiler that would permit such an algorithm?

How do you reduce algorithms that use non-polynomial space?


Comments

Post a Comment

Popular posts from this blog

thoughts on college

Hello faithful reader! I wanted a centralized location for my musings. The hardest challenge was naming! So many abandoned blogs with cool names. Reminds me of a frequently stolen (mis)quote: There are only two hard things in Computer Science: naming things. [ attribution ] -: school :- I started taking classes again today. I'm a functioning adult, pay bills, have a family. And on some level it's like I'm in high-school again. Being on this side of it - it's actually a pleasant awkwardness -: pondering :- I watched a YouTube video on creativity - John Cleese on Creativity [ link ]. My favorite part was the reminder to leave space to be creative. Whether writing a novel, or solving a difficult problem, we need to give ourselves time. In our modern instant-feedback society, it is a good reminder to trust the process. -: idea :- Given the notion of probabilistic circuitry, I wonder if it would be possible to use machine learning to design or build a circuit that could dra...
Post a Comment
Read more

thoughts on burial

Hello faithful reader! I was recently reading the bible and ruminating on Genesis. In Genesis 22, you have Abraham offering Isaac for a sacrifice. At the end of the chapter, a concubine is mentioned: Reumah. The first few times I read this, I thought this was Abraham's concubine; it felt like a bit of a betrayal of Sarah. This seemed further compounded by the fact the next time she's mentioned is her burial. I will have to confirm - but the internet seems to think this was not Abraham's concubine. Perhaps this was God's will - having two children from whom would come many nations was enough. However, the main item I wanted to mention was Sarah's gravesite. Abraham ultimately bought a small cave, and a field, for about $100,000 (400 shekels) [ link ]. I find this interesting for several reasons. The first - that Abraham pays for a burial site. I'm not sure if this was because he didn't want his wife buried on his own land or that perhaps his culture preferred...
Post a Comment
Read more

thoughts on distraction

Hello faithful reader! I like to-do lists. They add order to the world and help me prioritize my time. They also gird me against being distracted. This is important because I am exceptionally able to be distracted. And I think most of us are. Given a simple situation, most of us can tell you what action we should take. However, with a little duress, a little distraction - and any one of us can be nudged in a direction we'd never normally take. The simplest, though, is simply distraction. Maybe it's letting urgent things supersede important things. Maybe it's just one more level or quest on your game before you start. Maybe it's finishing the chapter in your book before you finish your homework. Biblically, Esau [ Genesis 25 ] got distracted and traded away his birthright. The execution of this was a few chapters later - which is also how distraction works. You don't normally notice when it's happening. -: anxious :- I find it hard to focus on important things - ...
Post a Comment
Read more